package cc.wsyw126.java.nowcoder.sword_offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by dp on 2017/4/19.
 * 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
 */
public class PrintInZ {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) return result;

        TreeNode temp = pRoot;
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode flag = new TreeNode(Integer.MIN_VALUE);
        q.add(pRoot);
        q.add(flag);
        int count = 0;
        ArrayList<TreeNode> nodes = new ArrayList<>();
        while (!q.isEmpty()) {
            TreeNode poll = q.poll();
            if (poll == flag) {
                ArrayList<Integer> integers = new ArrayList<>();

                int i = count % 2;
                if (i == 1) {
                    for (int i1 = 0; i1 < nodes.size(); i1++) {
                        integers.add(nodes.get(i1).val);
                    }

                } else {
                    for (int i1 = nodes.size() - 1; i1 >= 0; i1--) {
                        integers.add(nodes.get(i1).val);
                    }
                }
                result.add(integers);
                count++;
                nodes.clear();
                if (q.isEmpty())break;
                q.add(poll);
            }else {
                nodes.add(poll);
                if (poll.left!=null) q.add(poll.left);
                if (poll.right!=null) q.add(poll.right);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        //8,6,10,5,7,9,11
        TreeNode treeNode8 = new TreeNode(8);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode10 = new TreeNode(10);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode11 = new TreeNode(11);

        treeNode8.left=treeNode6;treeNode8.right=treeNode10;
        treeNode6.left=treeNode5;
        treeNode6.right=treeNode7;
        treeNode10.left=treeNode9;
        treeNode10.right=treeNode11;
        PrintInZ printInZ = new PrintInZ();
        ArrayList<ArrayList<Integer>> print = printInZ.Print(treeNode8);
        for (ArrayList<Integer> integers : print) {
            for (Integer integer : integers) {
                System.out.print(integer+"\t");
            }
            System.out.println();
        }
    }

}
